#include <iostream>
#include <ctime>
#include <cassert>
#include <string>
#include  <algorithm>
namespace SortTestHelper {

    template<typename T>
    bool isSorted(T arr[], int n) 
    {
        for(int i = 0; i < n -1; i++) {
            if(arr[i] > arr[i+1]) {
                return false;
            }
        }

        return true;
    }

    int* generateRandomArray(int n, int rangeL, int rangeR)
    {
        assert(rangeL <= rangeR);
        int *arr = new int[n];
        srand(time(NULL));
        for(int i = 0; i < n; i ++) {
            arr[i] = rand() %(rangeR - rangeL + 1) + rangeL;
        }

        return arr;
    }

    int *copyIntArray(int a[], int n)
    {
        int *arr = new int[n];
        std::copy(a, a+n, arr);
        return arr;
    }

    template<typename T>
    void printArray(T arr[], int n) 
    {

        for (int i = 0; i < n; i++)
            std::cout << arr[i] << " ";
        std::cout << std::endl;
    }

    // 计算时间
    template<typename T>
    void testSort(std::string sortName, void(*sort)(T[], int), T arr[], int n) 
    {
        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();

        assert(isSorted(arr, n));


        std::cout<< sortName<< ":"<< double(endTime - startTime) / CLOCKS_PER_SEC<< " s"<<std::endl;
    }
    
    // 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据
    // swapTimes定义了数组的无序程度:
    // swapTimes == 0 时, 数组完全有序
    // swapTimes 越大, 数组越趋向于无序
    int *generateNearlyOrderedArray(int n, int swapTimes){

        int *arr = new int[n];
        for(int i = 0 ; i < n ; i ++ )
            arr[i] = i;

        srand(time(NULL));
        for( int i = 0 ; i < swapTimes ; i ++ ){
            int posx = rand()%n;
            int posy = rand()%n;
            std::swap( arr[posx] , arr[posy] );
        }

        return arr;
    }

    


}